Grokking Oracle Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Oracle Easy
Count Number of Pairs With Absolute Difference K (easy)
Solution: Count Number of Pairs With Absolute Difference K
Degree of an Array (easy)
Solution: Degree of an Array
Find Subsequence of Length K With the Largest Sum (easy)
Solution: Find Subsequence of Length K With the Largest Sum
Rectangle Overlap (easy)
Solution: Rectangle Overlap
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Island Perimeter (easy)
Solution: Island Perimeter
Climbing Stairs (easy)
Solution: Climbing Stairs
Move Zeroes (easy)
Solution: Move Zeroes
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Valid Parentheses (Easy)
Solution: Valid Parentheses
Oracle Medium
Longest Palindromic Substring (medium)
Solution: Longest Palindromic Substring
Single Element in a Sorted Array (medium)
Solution: Single Element in a Sorted Array
Pairs of Songs With Total Durations Divisible by 60 (medium)
Solution: Pairs of Songs With Total Durations Divisible by 60
Search a 2D Matrix II (medium)
Solution: Search a 2D Matrix II
Minimize Maximum of Array (medium)
Solution: Minimize Maximum of Array
Asteroid Collision (medium)
Solution: Asteroid Collision
Combination Sum (medium)
Solution: Combination Sum
Binary Tree Right Side View (medium)
Solution: Binary Tree Right Side View
Sort Colors (medium)
Solution: Sort Colors
Group Anagrams (Medium)
Solution: Group Anagrams
Decode String (Medium)
Solution: Decode String
Number of Islands (medium)
Solution: Number of Islands
Binary Tree Zigzag Level Order Traversal (medium)
Solution: Binary Tree Zigzag Level Order Traversal
Longest Common Subsequence (medium)
Solution: Longest Common Subsequence
Rotting Oranges (medium)
Solution: Rotting Oranges
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Spiral Matrix (medium)
Solution: Spiral Matrix
Container With Most Water (Medium)
Solution: Container With Most Water
3Sum (medium)
Solution: 3Sum
Simplify Path (medium)
Solution: Simplify Path
Next Permutation (medium)
Solution: Next Permutation
Basic Calculator II (medium)
Solution: Basic Calculator II
Merge Intervals (medium)
Solution: Merge Intervals
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Longest Increasing Subsequence (medium)
Solution: Longest Increasing Subsequence
Validate Binary Search Tree (medium)
Solution: Validate Binary Search Tree
Integer to English Words (hard)
Solution: Integer to English Words
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Merge K Sorted Lists (hard)
Solution: Merge K Sorted Lists
Max Points on a Line (hard)
Solution: Max Points on a Line
Sudoku Solver (hard)
Solution: Sudoku Solver
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Constrained Subsequence Sum (hard)
Solution: Constrained Subsequence Sum
Solution: Search a 2D Matrix II

Problem Statement

Given a 2D grid of size m x n matrix containing integers, and integer target, return true if target value exists in the matrix. Otherwise, return false.

The matrix has the following properties:

  • Values in each column are sorted in non-decreasing order from top to bottom.
  • Values in each row are sorted in non-decreasing order from left to right.

Examples

Example 1:

  • Input: target = 5, matrix =
[[1,2,3],
 [4,5,6],
 [7,8,9]]
  • Expected Output: true
  • Justification: The number 5 is located in the second row and second column of the matrix, thus the output is true.

Example 2:

  • Input: target = 19, matrix =
[[10,11,12,13],
 [11,12,13,17],
 [14,19,22,24],
 [22,23,24,25]]
  • Expected Output: true
  • Justification: 19 is present in the third row and second column, confirming its presence in the matrix.

Example 3:

  • Input: target = 6, matrix =
[[1,3,5],
 [7,9,11],
 [13,15,17]]
  • Expected Output: false
  • Justification: 6 does not appear anywhere in the matrix, so the function should return false.

Solution

To solve this problem, we'll employ a strategic approach that leverages the sorted nature of the matrix to efficiently search for the target. Starting from the top-right corner of the matrix, we compare the target with the current element. If the target is larger, we move down a row, and if it's smaller, we move left a column. This process is repeated until the target is found or the limits of the matrix are exceeded.

This approach is effective because it eliminates one row or one column during each comparison, significantly reducing the search space. By starting at the top-right (or alternatively, bottom-left) corner, we can make a decision at each step that guides us closer to the target's location. This method is more efficient than linearly searching each row or column, or performing a binary search in each row or column, especially in large matrices.

Step-by-Step Algorithm

  1. Initialization: Start by checking if the matrix is empty or has no rows/columns. If so, return false as the target cannot be found in an empty matrix.
  2. Set Starting Point: Position yourself at the top right corner of the matrix. This is done by setting the row index to 0 (first row) and the column index to the index of the last column (matrix[0].length - 1).
  3. Iterative Search:
    • While your current position is within the bounds of the matrix (row index is less than the number of rows and column index is non-negative):
      • Compare Target with Current Element: If the current element (the one at your position) equals the target, return true as the target has been found.
      • Move Downwards: If the current element is less than the target, move down one row to increase the value (since rows are sorted in ascending order). This is done by incrementing the row index.
      • Move Leftwards: If the current element is greater than the target, move left one column to decrease the value (since columns are sorted in ascending order). This is done by decrementing the column index.
  4. Target Not Found: If the loop terminates without returning true, it means the target is not present in the matrix. Return false.

Algorithm Walkthrough

For the input matrix:

[[10,11,12,13],
 [11,12,13,17],
 [14,19,22,24],
 [22,23,24,25]]

target = 19

  1. Initialization: The matrix is not empty, so we proceed.
  2. Set Starting Point: Start at the top right corner, which is element 13 (row = 0, col = 3).
  3. Iterative Search:
    • Step 1: 13 is less than 19, so move down to increase the value (row = 1, col = 3).
    • Step 2: Now at 17 (row = 1, col = 3), which is still less than 19. Move down again (row = 2, col = 3).
    • Step 3: Now at 24 (row = 2, col = 3), which is greater than 19. Move left to decrease the value (row = 2, col = 2).
    • Step 4: Now at 22 (row = 2, col = 2), which is still greater than 19. Move left again (row = 2, col = 1).
    • Step 5: Now at 19 (row = 2, col = 1), which equals the target. Return true.
  4. Conclusion: The target 19 is found in the matrix, so the algorithm returns true.

Code

Java

. . . .

Complexity Analysis

  • Time Complexity: The algorithm has a time complexity of , where m is the number of rows and n is the number of columns in the matrix. This is because, in the worst-case scenario, the algorithm will travel from the top-right corner to the bottom-left corner, traversing at most m + n - 1 elements.

  • Space Complexity: The space complexity is as the algorithm only uses a constant amount of space regardless of the input size.

Search a 2D Matrix II (medium)
Minimize Maximum of Array (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis